package com.cat.dataStructure03;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/sliding-puzzle/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/11/3 18:04
 * @since JDK17
 */

public class Solution09 {
    static int[][] dire = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    List<Integer> toList(int[][] mat) {
        return Arrays.stream(mat).flatMapToInt(Arrays::stream).boxed().toList();
    }

    int[][] toArray(List<Integer> list) {  // 列表转换为数组
        int[][] mat = new int[2][3];
        for (int i = 0; i < 6; i++) {
            mat[i / 3][i % 3] = list.get(i);
        }
        return mat;
    }

    void swap(int[][] mat, int x1, int y1, int x2, int y2) {
        int t = mat[x1][y1];
        mat[x1][y1] = mat[x2][y2];
        mat[x2][y2] = t;
    }

    boolean check(List<Integer> list) {
        for (int i = 0; i < 5; i++) {
            if (list.get(i) != i + 1) {
                return false;
            }
        }
        return true;
    }

    public int slidingPuzzle(int[][] board) {
        Set<List<Integer>> set = new HashSet<>();
        List<List<Integer>> q = new ArrayList<>();
        int ans = 0;
        var start = toList(board);
        set.add(start);
        q.add(start);
        while (!q.isEmpty()) {
            var t = new ArrayList<>(q);
            q = new ArrayList<>();
            for (int i = 0; i < t.size(); i++) {
                var state = t.get(i);
                if (check(state)) {
                    return ans;
                }
                int r = 0, c = 0;
                for (int j = 0; j < 6; j++) {   // 找到零位置
                    if (state.get(j) == 0) {
                        r = j / 3;
                        c = j % 3;
                        break;
                    }
                }
                var mat = toArray(state);   //
                for (var d : dire) {
                    int x = r + d[0], y = c + d[1];
                    if (x >= 0 && x < 2 && y >= 0 && y < 3) {
                        swap(mat, r, c, x, y);  // 交换位置
                        if (set.add(toList(mat))) {
                            q.add(toList(mat));
                        }
                        swap(mat, r, c, x, y);
                    }
                }
            }

            ans++;
        }
        return -1;
    }
}
